
//30.串联所有的单词的子串
class Solution {
    public:
        //words中字符串给长度相同是重要信息
        //先将words放入到set中去，方便判断子字符串是否满足条件
    
        vector<int> findSubstring(string s, vector<string>& words) {
            int num=words.size(),len=words[0].size();  //用num来表示有多少个子字符串，len表示每一个字符串长度
            int n=s.size();
            if(n<num*len) return {}; //s长度比words总长小直接返回
    
            vector<int> ret;
            for(int k=0;k<len;k++)  //采用滑动窗口的方式进行，进单词--判断--出单词，要特别注意的是的第一个单词开始的位置
            {
                unordered_map<string,int> all;     //int记录区间内单词与目标的单词个数差
                for(auto e:words)
                all[e]--;  
    
                int left=k,right=k;
                //先将num-1个单词入窗口，因为在后面循环中每次入单词和出单词都是对一个单词进行操作
                for(int i=0;i<num-1;i++)
                {
                    if(right+len>n) break;   //防止结尾处不能满足一个单词
                    string tmp=s.substr(right,len);
                    if(++all[tmp]==0) all.erase(tmp);  //差为0，就从map中删除
                    right+=len;
                }
            
                while(right<n)
                {
                    //进行入窗口,再入一个单词
                    if(right+len>n) break;
                    string tmp=s.substr(right,len);
                    if(++all[tmp]==0) all.erase(tmp); 
                    right+=len;
    
                    //更新答案
                    if(all.empty()) ret.push_back(left);
                    //出窗口
                    tmp=s.substr(left,len);
                    if(--all[tmp]==0) all.erase(tmp); 
                    left+=len;
                }
            }
            return ret;
        }
    };